#
# @lc app=leetcode.cn id=746 lang=python3
#
# [746] 使用最小花费爬楼梯
#

# @lc code=start
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # 1.确定状态
        # 最后一步:支付 1 ，向上爬一个台阶，到达楼梯顶部n。
        # cost=1 dp[9]=min(dp[8]+cost[8],dp[7]+cost[7])=dp[8]+cost[8]=dp[8]+1
        # 子问题:dp[8]=dp[9]-1
        # 2.转移方程
        # dp[n]=min(dp[n-1]+cost[n-1], dp[n-2]+cost[n-2])
        # 3.初始条件和边界情况
        # dp[0]=0,dp[1]=0 [0,len(cost)]
        # 4.循环顺序
        # 台阶数 i [2,n]
        n = len(cost)+1
        dp = [0]*n
        for i in range(2, n):
            dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
            # print(f'dp[{i}]={dp[i]}', end=' ')
            # print(f'dp[{i-1}]+cost[{i-1}]={dp[i-1]}+{cost[i-1]}={dp[i-1]+cost[i-1]}', end=' ')
            # print(f'dp[{i-2}]+cost[{i-2}]={dp[i-2]}+{cost[i-2]}={dp[i-2]+cost[i-2]}')
        return dp[n-1]
# @lc code=end

